/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/edit-distance
   @Language: C++
   @Datetime: 16-02-09 05:48
   */

// Method 1, Time O(m*n), Space O(m*n)
class Solution {
public:
	/**
	 * @param word1: A string
	 * @param word2: A string
	 * @return: The minimum number of steps.
	 */
	int minDistance(string &word1, string &word2) {
		// write your code here
		int l1=word1.length(), l2=word2.length();
		if(l1==0 || l2==0) return l1==0?l2:l1;
		vector<vector<int> > dp(l1+1,vector<int>(l2+1,0));
		for(int i=l2+1; i--; dp[0][i]=i);
		for(int i=1; i<=l1; ++i){
			dp[i][0]=i;
			for(int j=1; j<=l2; ++j){
				int replace=dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1);
				int insertion=dp[i][j-1]+1;
				int deletion=dp[i-1][j]+1;
				dp[i][j]=min(replace,min(insertion,deletion));
			}
		}
		return dp[l1][l2];
	}
};


// Method 2, Time O(m*n), Space(n)
class Solution {
public:
	/**
	 * @param word1: A string
	 * @param word2: A string
	 * @return: The minimum number of steps.
	 */
	int minDistance(string &word1, string &word2) {
		// write your code here
		int l1=word1.length(), l2=word2.length();
		if(l1==0 || l2==0) return l1==0?l2:l1;
		vector<vector<int> > dp(2,vector<int>(l2+1,0));
		for(int i=l2+1; i--; dp[0][i]=i);
		for(int i=1; i<=l1; ++i){
			dp[i&1][0]=i;
			for(int j=1; j<=l2; ++j){
				int replace=dp[(i-1)&1][j-1]+(word1[i-1]==word2[j-1]?0:1);
				int insertion=dp[i&1][j-1]+1;
				int deletion=dp[(i-1)&1][j]+1;
				dp[i&1][j]=min(replace,min(insertion,deletion));
			}
		}
		return dp[l1&1][l2];
	}
};
